"""
70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=dynamic-programming
f(x)=f(x−1)+f(x−2)
"""
class Solution:
    def climbStairs(self, n: int) -> int:
        p = 0
        q = 0
        r = 1
        for i in range(n):
            p = q
            q = r
            r = p+q
        return r

print(Solution().climbStairs(2)) # 2
print(Solution().climbStairs(3)) # 3